package com.lin.houserobberiii;

/**
 * 打家劫舍3
 *
 * @author 九分石人
 */
public class HouseRobberIii {

    public int rob(TreeNode root) {
        int[] robb = robb(root);
        return Math.max(robb[0], robb[1]);
    }


    int[] robb(TreeNode root) {
        if (root == null) {
            return new int[2];
        }
        int[] result = new int[2];

        int[] left = robb(root.left);
        int[] right = robb(root.right);

        //不选当前节点，则选左子树的最大值加右子树的最大值
        result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        //选当前节点，则为不选左子树加不选右子树加自己的值
        result[1] = left[0] + right[0] + root.val;

        return result;
    }
}
